/**
 * 509. 斐波那契数
 * https://leetcode.cn/problems/fibonacci-number/description/
 */

//动态规划
class Solution {
    int[] dp;
    public int fib(int n) {
        dp = new int[31];
        dp[0] = 0; dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

// //记忆化搜索
// class Solution {
//     int[] memory;//备忘录
//     public int fib(int n) {
//         memory = new int[31];
//         for(int i = 0; i < 31; i++) {
//             memory[i] = -1;
//         }
//         return dfs(n);
//     }
//     public int dfs(int n) {
//         //判断备忘录里面有没有记录
//         if(memory[n] != -1) {
//             return memory[n];
//         }
//         if(n == 0 || n == 1) {
//             memory[n] = n; //记录到备忘录里
//             return n;
//         }
//         memory[n] = dfs(n - 1) + dfs(n - 2); //记录到备忘录里
//         return memory[n];
//     }
// }